package main;

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;

/**
 * @Author: 谢焕涛
 * @Description: OptimizedMaximalSolutionSolver
 * @Date: 2025/5/13 上午9:56
 * @Version: 1.0
 */
public class OptimizedMaximalSolutionSolver {
    private static final int SCALE = 10000; // 精度提升至4位小数

    public static void main(String[] args) {
        // 示例参数（与图片完全一致）
        double[] coefficients = {
                parseFraction("1/20"),
                parseFraction("1/33"),
                parseFraction("3/20")
        };
        int[] minValues = {7, 10, 1};

        solveMaximalSolutions(coefficients, 1.0, minValues);
    }

    // 分数解析器避免浮点误差
    private static double parseFraction(String fraction) {
        String[] parts = fraction.split("/");
        return Double.parseDouble(parts[0]) / Double.parseDouble(parts[1]);
    }

    public static void solveMaximalSolutions(double[] n, double a, int[] minValues) {
        // ---- 精度转换 ----
        int[] N = new int[n.length];
        BigDecimal sumMinBD = BigDecimal.ZERO;

        // 使用BigDecimal精确计算
        for (int i = 0; i < n.length; i++) {
            BigDecimal ni = new BigDecimal(n[i])
                    .multiply(new BigDecimal(SCALE))
                    .setScale(0, RoundingMode.HALF_UP);
            N[i] = ni.intValueExact();

            BigDecimal minTerm = ni.multiply(new BigDecimal(minValues[i]));
            sumMinBD = sumMinBD.add(minTerm);
        }

        int A = new BigDecimal(a).multiply(new BigDecimal(SCALE)).intValueExact();
        int sumMin = sumMinBD.intValueExact();
        int A_prime = A - sumMin;

        // ---- 动态规划优化 ----
        Map<Integer, Set<Solution>> dp = new HashMap<>();
        dp.put(0, new HashSet<>(Collections.singleton(new Solution(new int[n.length]))));

        for (int i = 0; i < N.length; i++) {
            Map<Integer, Set<Solution>> newDp = new HashMap<>();
            int Ni = N[i];
            int row = i;

            dp.forEach((sum, solutions) -> {
                solutions.forEach(comb -> {
                    int maxM = (A_prime - 1 - sum) / Ni;
                    for (int m = 0; m <= maxM; m++) {
                        int newSum = sum + m * Ni;
                        int[] newComb = comb.copyWithIncrement(row, m);

                        newDp.computeIfAbsent(newSum, k -> new HashSet<>())
                                .add(new Solution(newComb));
                    }
                });
            });
            dp = mergeStates(newDp); // 合并相同总和的解
        }

        // ---- 临界解过滤 ----
        List<Solution> maximalSolutions = new ArrayList<>();
        dp.values().forEach(solutions -> {
            solutions.forEach(comb -> {
                if (isMaximal(comb, N, A_prime)) {
                    maximalSolutions.add(comb);
                }
            });
        });

        // ---- 结果输出 ----
        printSolutions(maximalSolutions, minValues, N, SCALE);
    }

    // 判断是否为临界解（并行加速）
    private static boolean isMaximal(Solution comb, int[] N, int A_prime) {
        return Arrays.stream(N)
                .anyMatch(ni -> comb.calculateSumWithIncrement(N, ni) >= A_prime);
    }

    // 合并相同总和的解（优化内存）
    private static Map<Integer, Set<Solution>> mergeStates(Map<Integer, Set<Solution>> states) {
        Map<Integer, Set<Solution>> merged = new HashMap<>();
        states.forEach((sum, solutions) ->
                merged.computeIfAbsent(sum, k -> new HashSet<>()).addAll(solutions));
        return merged;
    }

    // 输出结果（保留与图片相同的格式）
    private static void printSolutions(List<Solution> solutions, int[] minValues,
                                       int[] N, int scale) {
        System.out.println("临界解集（共 " + solutions.size() + " 种）：");
        solutions.forEach(comb -> {
            int[] vars = comb.restoreVariables(minValues);
            double loss = calculateLoss(vars, N, scale);
            System.out.printf("x=%d y=%d z=%d | 损耗:%.4f卷 | 约%d米%n",
                    vars[0], vars[1], vars[2],
                    loss, Math.round(loss * 130)); // 130米/卷系数
        });
    }

    private static double calculateLoss(int[] vars, int[] N, int scale) {
        BigDecimal total = BigDecimal.ZERO;
        for (int i = 0; i < vars.length; i++) {
            BigDecimal term = new BigDecimal(N[i])
                    .multiply(new BigDecimal(vars[i]))
                    .divide(new BigDecimal(scale), 8, RoundingMode.HALF_UP);
            total = total.add(term);
        }
        BigDecimal loss = BigDecimal.ONE.subtract(total);
        return loss.setScale(8, RoundingMode.HALF_UP).doubleValue();
    }

    // 辅助类封装组合状态
    private static class Solution {
        private final int[] increments;

        Solution(int[] increments) {
            this.increments = increments.clone();
        }

        int[] copyWithIncrement(int index, int value) {
            int[] newArr = increments.clone();
            newArr[index] += value;
            return newArr;
        }

        int[] restoreVariables(int[] minValues) {
            int[] res = new int[minValues.length];
            for (int i = 0; i < res.length; i++) {
                res[i] = minValues[i] + increments[i];
            }
            return res;
        }

        int calculateSumWithIncrement(int[] N, int index) {
            // 校验索引合法性
            if (index < 0 || index >= N.length) {
                throw new IllegalArgumentException("Index must be within [0, " + (N.length-1) + "]");
            }
            int sum = 0;
            for (int i = 0; i < N.length; i++) {
                sum += N[i] * increments[i];
            }
            return sum + N[index];
        }

        @Override
        public boolean equals(Object o) {
            return Arrays.equals(increments, ((Solution) o).increments);
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(increments);
        }
    }
}
